package NiuKe.TwoSerch;

/**
 *二分查找的专项练习
 * 链接:https://www.nowcoder.com/exam/oj?page=1&tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
 */
 class Solution {
    /**
     * 1：请实现无重复数字的升序数组的二分查找
     */
    public int search (int[] nums, int target) {
        // write code here
        int left=0;
        int right=nums.length-1;
        int mid=(left+right)/2;
        while(left <= right){
            if(nums[mid] > target){
                right=mid-1;
                mid=(left+right)/2;

            }
            else if(nums[mid] < target){
                left=mid+1;
                mid=(left+right)/2;
            }else{
                return mid;
            }

        }
        return -1;
    }

    /**二维数组中的查找
     2:在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
     * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     * 解题思路:利用1实现的二分查找遍历二维数组
     */
    public boolean Find(int target, int [][] array) {
        int [] tmp;
        Solution T1=new Solution();
        for (int i = 0; i < array.length; i++) {
            tmp=array[i];
            int X=0;
            X=T1.search(tmp,target);
            if (X != -1){
                return true;
            }
        }
        return false;

    }

    /** 寻找峰值
     3:给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
     */
   /* public int my_findPeakElement (int[] nums) {
        // 自己写的垃圾，虽然通过了
        if(nums.length == 0){
            return 0;
        }
        if (nums.length<3){
            if(nums.length == 1){
                return 0;
            }
            if (nums[0]<nums[1]){
                return 1;
            }else{
                return 0;
            }
        }
        int left=0;
        int right=nums.length-1;
        int mid=(left+right)/2;
        for (int i = 1; i < mid; i++) {
            int A=nums[i-1];
            int B=nums[i+1];
            if (nums[i]>A && nums[i]>B){
                return i;
            }
        }
        for (int i = mid; i < right; i++) {
            int A=nums[i-1];
            int B=nums[i+1];
            if (nums[i]>A && nums[i]>B){
                return i;
            }

        }
        if(nums[right]>nums[right-1]){
            return right;
        }
        return 0;
    }*/

    /**
     * 因为题目将数组边界看成最小值，而我们只需要找到其中一个波峰，因此只要不断地往高处走，一定会有波峰。
     * 那我们可以每次找一个标杆元素，将数组分成两个区间，每次就较高的一边走，因此也可以用分治来解决，而标杆元素可以选择区间中点。
     * 本质上，是找最大值么
     */

    public int findPeakElement (int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        //二分法
        while(left < right){
            int mid = (left + right) / 2;
            //右边是往下，不一定有坡峰
            if(nums[mid] > nums[mid + 1])
                right = mid;
                //右边是往上，一定能找到波峰
            else
                left = mid + 1;
        }
        //其中一个波峰
        return right;
    }
    /*旋转数组的最小数字
    4:有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，
    比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
    解题思路:二分查找*/
    public int minNumberInRotateArray(int [] array) {
        int j=array.length/2;
        int min=Integer.MAX_VALUE;
        for (int i = 0; i < array.length/2; i++) {
            if (min>array[i])min=array[i];
            if (min>array[j])min=array[j];
            j++;
        }
        return min;
    }
//    比较版本号
//    解题思路:挨个遍历,遇到"."跳过
    public int compare (String version1, String version2) {
        int n1 = version1.length();
        int n2 = version2.length();
        int i = 0, j = 0;
        //直到某个字符串结束
        while(i < n1 || j < n2){
            long num1 = 0;
            //从下一个点前截取数字
            while(i < n1 && version1.charAt(i) != '.'){
                num1 = num1 * 10 + (version1.charAt(i) - '0');
                i++;
            }
            //跳过点
            i++;
            long num2 = 0;
            //从下一个点前截取数字
            while(j < n2 && version2.charAt(j) != '.'){
                num2 = num2 * 10 + (version2.charAt(j) - '0');
                j++;
            }
            //跳过点
            j++;
            //比较数字大小
            if(num1 > num2)
                return 1;
            if(num1 < num2)
                return -1;
        }
        //版本号相同
        return 0;
    }
}

